package BackTracking.combination;//找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
//
// 说明： 
//
// 
// 所有数字都是正整数。 
// 解集不能包含重复的组合。 
// 
//
// 示例 1: 
//
// 输入: k = 3, n = 7
//输出: [[1,2,4]]
// 
//
// 示例 2: 
//
// 输入: k = 3, n = 9
//输出: [[1,2,6], [1,3,5], [2,3,4]]
// 
// Related Topics 数组 回溯 👍 386 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class combinationSum3 {

    List<List<Integer>> res = new ArrayList<>();  //结果集
    List<Integer> nums = new ArrayList<>();  //回溯路径集
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        /**
         * 回溯
         * 可以看出 有三个要求，数字只能从1-9中选择，且只能选k个，和必须为n
         * 剪枝优化可在  选择数字的个数上和选择的大小上进行优化
         * */
        backTracking(k, n, 1);
        return res;

    }

    private void backTracking(int k, int n, int startIndex){
        //剪枝 当前和已经大于目标值时，没必要再进行
        if(sum>n){
            return;
        }
        //当数字集大小、和满足要求
        // k控制的是递归走的深度，当到一定深度不符合要求则返回上层，符合要求则加入结果集
        if(nums.size()==k){
            if(sum==n){
                res.add(new ArrayList<>(nums));
            }
            return;
        }
        //选择回溯
        for (int i = startIndex; i <= 9-(k-nums.size())+1; i++) {
            nums.add(i);  //添加
            sum += i;
            backTracking(k, n,i+1);  //递归
            nums.remove(nums.size()-1);  //回溯
            sum -= i;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
